package cxydmmszl.chapter02.t014;

/**
 * <li style="color: red;">Prob</li>
 * 删除链表的中间节点和 a/b 处的节点
 * <li style="color: red;">Desc</li>
 * 给定链表的头节点 head，实现删除链表的中间节点的函数。<br/>
 * 例如：<br/>
 * &emsp;null，不删除任何节点；<br/>
 * &emsp;1->2，删除节点 1；<br/>
 * &emsp;1->2->3，删除节点 2；<br/>
 * &emsp;1->2->3->4，删除节点 2；<br/>
 * &emsp;1->2->3->4->5，删除节点 3；<br/><br/>
 * 给定链表的头节点 head、整数 a、b，实现删除位于 a/b 处节点的函数。<br/>
 * 例如：<br/>
 * &emsp;链表：1->2->3->4->5，假设 a/b 的值为 r。<br/>
 * &emsp;如果 r=0，不删除任何节点；<br/>
 * &emsp;如果 r 在区间 (0, 1/5] 上，删除节点 1；<br/>
 * &emsp;如果 r 在区间 (1/5, 2/5] 上，删除节点 2；<br/>
 * &emsp;如果 r 在区间 (2/5, 3/5] 上，删除节点 3；<br/>
 * &emsp;如果 r 在区间 (3/5, 4/5] 上，删除节点 4；<br/>
 * &emsp;如果 r 在区间 (4/5, 1] 上，删除节点 5；<br/>
 * &emsp;如果 r>0，不删除任何节点；<br/>
 *
 * <li style="color: red;">Link</li>
 *
 * @author habitplus
 * @since 2021-08-27 22:30
 */
public class Main {
    private static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    public Node removeMidNode(Node head) {
        if (head == null || head.next == null) {
            return null;
        }
        Node tou = new Node(0);
        tou.next = head;
        Node fast = head.next, slow = tou;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;

        return tou.next;
    }

    public Node removeNodeByRatio(Node head, int a, int b) {
        if (head == null || a < 1 || a > b) {
            return head;
        }

        // 求出链表的长度
        int k = 0;
        Node assist = head;
        while (assist != null) {
            assist = assist.next;
            k++;
        }

        k = (int) Math.ceil(((double) (a * k)) / b);

        if (k == 1) {
            head = head.next;
        } else if (k > 1) {
            assist = head;
            while (--k != 1) {
                assist = assist.next;
            }
            assist.next = assist.next.next;
        }

//        Node tou = new Node(0);
//        tou.next = head;
//        assist = tou;
//        if (k >= 1) {
//            while (k > 1) {
//                assist = assist.next;
//                k--;
//            }
//            assist.next = assist.next.next;
//        }
//        return tou.next;

        return head;
    }
}
